//
// Created by liushuai on 2021/1/1.
//

#include "merge.h"

void merge(vector<int> &nums1, int m, vector<int> &nums2, int n) {
<<<<<<< HEAD:cxx/algorithm/src/merge.cc
    int last_index = m + n - 1;
    int num_index1 = m - 1;
    int num_index2 = n - 1;
    if (num_index1 < 0) {
        for (int i = 0; i <= m; i++)
            nums1[i] = nums2[i];
    }
    while (num_index1 >= 0 && num_index2 >= 0 & last_index >= 0) {
        if (nums1[num_index1] < nums2[num_index2]) {
            nums1[last_index--] = nums2[num_index2];
            num_index2--;
        } else {
            nums1[last_index--] = nums1[num_index1];
            num_index1--;
        }
    }
    while (num_index2 >= 0) {
        nums1[num_index2] = nums2[num_index2];
        num_index2--;
    }
}

vector<vector<int>> merge(vector<vector<int>> &intervals) {
    vector<vector<int>> res;
    if (intervals.empty())
        return res;
    std::sort(intervals.begin(), intervals.end());
    int start = intervals[0][0];
    int end = intervals[0][1];
    for (int i = 1; i < intervals.size(); i++) {
        int current_start = intervals[i][0];
        int current_end = intervals[i][1];
        if (current_start <= end) {
            end = std::max(current_end,end);
        } else {
            res.push_back({start, end});
            start = current_start;
            end = current_end;
        }
    }
    res.push_back({start, end});
    return res;
=======
  int last_index = m + n - 1;
  int num_index1 = m - 1;
  int num_index2 = n - 1;
  if (num_index1 < 0) {
    for (int i = 0; i <= m; i++) nums1[i] = nums2[i];
  }
  while (num_index1 >= 0 && num_index2 >= 0 & last_index >= 0) {
    if (nums1[num_index1] < nums2[num_index2]) {
      nums1[last_index--] = nums2[num_index2];
      num_index2--;
    } else {
      nums1[last_index--] = nums1[num_index1];
      num_index1--;
    }
  }
  while (num_index2 >= 0) {
    nums1[num_index2] = nums2[num_index2];
    num_index2--;
  }
}

vector<vector<int>> merge(vector<vector<int>> &intervals) {
  vector<vector<int>> res;
  if (intervals.empty()) return res;
  std::sort(intervals.begin(), intervals.end());
  int start = intervals[0][0];
  int end = intervals[0][1];
  for (int i = 1; i < intervals.size(); i++) {
    int current_start = intervals[i][0];
    int current_end = intervals[i][1];
    if (current_start <= end) {
      end = std::max(current_end, end);
    } else {
      res.push_back({start, end});
      start = current_start;
      end = current_end;
    }
  }
  res.push_back({start, end});
  return res;
>>>>>>> dev:cxx/algorithm/common/src/merge.cc
}